package linkedlist;

class ListNode{
    int val;
    ListNode next;
    ListNode(){

    }
    ListNode (int val){
        this.val = val;
    }
    ListNode (int val,ListNode next){
        this.val = val;
        this.next = next;
    }
}
//根据元素值删除链表中所有与该元素相同的元素,并返回头节点
//先不判断头节点,因为可能判断完头节点符合并删除,下一个节点就变成了头节点,可能仍然需要删除,就非常麻烦
//public class LinkedListProblem1 {
//    public ListNode removeElements(ListNode head,int val){
//        if(head == null){
//            return null;
//        }
//        ListNode prev = head;
//        ListNode cur = head.next;
//
//        while(cur != null){
//            if(cur.val == val){
//                prev.next = cur.next;
//                cur = prev.next;
//            }else{
//                prev = cur;
//                cur = cur.next;
//            }
//        }
//        //最后再判断头节点是否为空
//        if(head == null){
//            head = head.next;
//        }
//        return head;
//    }
//}

//反转链表,并返回头节点
//public class LinkedListProblem1 {
//    public ListNode removeElements(ListNode head,int val){
//        //空的和只有一个元素的,都不用进行反转
//        if(head == null){
//            return null;
//        }
//        if(head.next == null){
//            return head;
//        }
//        ListNode newhead = null;
//        ListNode prev = null;//为了记录cur后的元素,防止丢失
//        ListNode cur = head;
//        ListNode next = cur.next;
//        while(cur != null){
//            //每一轮cur的位置都不一样,因此需要重新存储
//            next = cur.next;
//            //第一轮指向null,就变成了尾节点
//            cur.next = prev;
//            if(next == null){
//                newhead = cur;
//            }
//            prev = cur;
//            cur = next;
//        }
//        return newhead;
//    }
//}

//返回链表的中间节点
//public class LinkedListProblem1 {
//    public ListNode middleNode(ListNode head){
//        //判定链表为空
//        if(head == null){
//            return null;
//        }
//        int size = size(head);
//        ListNode cur = null;
//        //从head出发,走size/2布即可
//        for(int i = 0;i < size / 2;i++){
//            cur = cur.next;
//        }
//        return cur;
//    }
//    public int size(ListNode head){
//        int size = 0;
//        for(ListNode cur = head;cur != null;cur = cur.next){
//            size++;
//        }
//        return size;
//    }
//}

//返回链表的倒数第k个节点的值
//public class LinkedListProblem1 {
//    public int kthToLast(ListNode head,int k) {
//        //从第一个节点开始走,需要走size - k步
//        if (head == null) {
//            return 0;
//            //抛出异常在oj中是不行的,因此只能return 0
//        }
//只有倒数第一步,没有倒数第零步
//        if (k <= 0 || k > size(head)) {
//            return 0;
//        }
//        int step = size(head) - k;
//        ListNode cur = head;
//走一步到第二个位置,两步到第三个位置,这个与普通的i++有所不同
//        for (int i = 0; i < step; i++) {
//            cur = cur.next;
//        }
//        return cur.val;
//    }
//    public int size(ListNode head){
//        int size = 0;
//        for(ListNode cur = head;cur != null;cur = cur.next){
//            size++;
//        }
//        return size;
//    }
//}
public class LinkedListProblem1 {
    public int kthToLast(ListNode head,int k){
        if(head == null){
            return 0;
        }
        //
        if(k <= 0 && k > size(head)){
            return 0;
        }
        int step = size(head) - k;
        ListNode cur = head;
        for(int i = 0;i < step;i++){
            cur = cur.next;
        }
        return cur.val;
    }
    public int size(ListNode head){
        int size = 0;
        for(ListNode cur = head;cur != null;cur = cur.next){
            size++;
        }
        return size;
    }
}




//按照从小到大的顺序合并两个链表
//public class LinkedListProblem1 {
//    //创建一个新链表,搞两个引用,比较两个引用的值,谁比较小,就把谁插入到新链表的末尾,
//    //当一个链表的引用指向null时,就把另一个链表所有的元素都插入到新链表中
//    public ListNode mergeTwoList(ListNode list1,ListNode list2){
//        if(list1 == null){
//            return list2;
//        }
//        if(list2 == null){
//            return list1;
//        }
//        ListNode cur1 = list1;
//        ListNode cur2 = list2;//注:这道题也可以直接拿list1和list2操作
//        // ,因为后面没有需要使用list1,list2的功能
//        ListNode newHead = new ListNode(0);
//        //创建傀儡节点
//        ListNode newTail = newHead;
//        while (cur1 != null&&cur2 != null){
//            //需要记录链表的尾巴,因为后续都是尾插
//            //为了更加简单,使用傀儡节点,这样后续的尾插会更加简单
//            if(cur1.val < cur2.val){
//                newTail.next = cur1;
//                newTail = cur1;
//                cur1 = cur1.next;
//            }else{
//                newTail.next = cur2;
//                newTail = cur2;
//                cur2 = cur2.next;
//            }
//        }
//        //一个完了,一个还有剩余的情况直接把剩下的都连到新链表的后面
//        if(cur1 != null){
//            newTail.next = cur2;
//        }
//        if(cur2 != null){
//            newTail.next = cur1;
//        }
//        return newHead.next;
//    }
//}


